/**
 * 
 */
package tree;

import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author Michael
 *
 */
public class ConvertSortedLinkedListToBalancedBST {


	// O(n) = n/2+2O(n/2) = O(n*log(n))?
	// boost to O(n): save the linked list nodes into an array in advance?
	public static <T extends Comparable<? super T>> tree.Node<T> convert(linkedlist.Node<T> head, int length) {
		if (null == head || length <= 0)
			return null;
		
		linkedlist.Node<T> midNode = head;
		for (int i = 0, size = length / 2; i < size; ++i) {
			midNode = midNode.next;
		}
		
		tree.Node<T> root = new tree.Node<T>(midNode.value);
		int leftLength = length / 2;
		int rightLength = length - leftLength - 1;
		
		root.left = convert(head, leftLength);
		root.right = convert(midNode.next, rightLength);
		
		return root;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int length = CreateUtils.randNonNegInt(20);
		linkedlist.Node<Integer> head = CreateUtils
				.sortedLinkedListFromOneToN(length);
		tree.Node<Integer> root = convert(head, length);
		PrintUtils.printLinkedList(head);
		PrintUtils.printBinaryTree(root);
	}

	/**
	 * 
	 */
	public ConvertSortedLinkedListToBalancedBST() {
		// TODO Auto-generated constructor stub
	}
}
